package cn.rocky.structures.hash_table;


import java.util.LinkedList;

/**
 * 拉链寻址: 我们没法控制元素不碰撞,但我们可以对碰撞后的元素进行管理。比如像HashMap中的拉链法一样,把碰撞但元素存放到链表上。
 */
public class HashMap02BySeparateChaining<K,V> implements Map<K,V>{

    private final LinkedList<Node<K, V>>[] tab = new LinkedList[8]; // 将碰撞元素存放到链表中

    static class Node<K, V> {
        final K key;
        V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

    }


    /**
     * 1.因为元素在存放到哈希桶上时，可能发生下标索引膨胀,所以这里我们把每一个元素都设定成一个Node节点,这些节点通过LinkedList链表关联,当然你也可以通过Node节点构建出链表next元素即可。
     * 2.那么这时候在发生元素碰撞,相同位置的元素就都存放到链表上了,获取的时候需要对多个元素的链表进行遍历获取。
     * @param key
     * @param value
     */
    @Override
    public void put(K key, V value) {
        int idx = key.hashCode() & (tab.length - 1);
        if (tab[idx] == null) {
            tab[idx] = new LinkedList<>();
            tab[idx].add(new Node<>(key, value));
        } else {
            tab[idx].add(new Node<>(key, value));
        }
    }

    @Override
    public V get(K key) {
        int idx = key.hashCode() & (tab.length - 1);
        for (Node<K, V> kvNode : tab[idx]) {
            if (key.equals(kvNode.getKey())) {
                return kvNode.getValue();
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Map<String, String> map = new HashMap02BySeparateChaining<>();
        map.put("01", "花花");
        map.put("02", "豆豆");
        System.out.println("碰撞前 key：" + "01"+" value：" + map.get("01"));
        System.out.println("碰撞前 key：" + "02"+" value：" + map.get("02"));

        // 下标碰撞
        map.put("09", "蛋蛋");
        map.put("13", "蛋蛋1");
        map.put("12", "苗苗");
        System.out.println("碰撞前 key：01 value：" + map.get("01"));
        System.out.println("碰撞前 key：" + "02"+" value：" + map.get("02"));
        System.out.println("碰撞前 key：01 value：" + map.get("09"));
    }
}
